1. Field of the Invention
This invention relates to the field of data processing systems. More particularly, this invention relates to data processing systems having a branch prediction mechanism and which may be subject to context switches.
2. Background
It is known to provide data processing systems with branch prediction mechanisms with a view to increasing the processing performance by correctly predicting branch instruction behaviour and so correctly fetching the appropriate sequence of program instructions before the branch instructions concerned are executed. One known mechanism for branch prediction provides a branch target buffer (BTB) which is operable to store an indication indexed by the fetch address as to whether or not instructions associated with that fetch address contain a taken branch instruction and if so what is the branch target address of that taken branch instruction. In this way, if instructions are being fetched from that address, then a prediction can be made that a branch to the associated branch target address will occur (assuming the behaviour is the same as the last time that branch instruction was encountered) and accordingly instruction fetching can be continued from the branch target address. Branch target buffers have become larger as the resources (e.g. gate count) to dedicate to such mechanisms have become more readily available within integrated circuits. Accordingly, a considerable volume of data concerning the previous branch behaviour of the system can be built up within the branch target buffer and a good level of prediction accuracy achieved. Mechanisms may also be provided dedicated to predicting conditional branches, e.g. a global history buffer (GHB).
Within data processing systems the fetch addresses may be physical addresses uniquely identifying a memory address within physical address space. Alternatively, the system may use virtual addresses to address a memory system with those virtual addresses then being translated into physical addresses within the memory system in order to return the appropriate instructions. The use of virtual memory addressing causes problems for branch target prediction in that when a context switch is made, such that the mapping between virtual addresses and the physical addresses is changed, a virtual address that is subsequently issued to fetch instructions from memory in the new context can incorrectly produce a hit within the branch target buffer relating to a taken branch instruction which was present at that same virtual address in the previous context. If that hit causes a misprediction and an inappropriate branch to be taken in the instruction fetching, then this needs to be identified and repaired.
One known technique for dealing with the problem of context switches within systems including virtual addressing and a branch target buffer is to flush the branch target buffer so as to invalidate all of its entries when a context switch occurs. Another known technique is to add a process identifier to each tag, and compare the current process identifier as part of the tag. However, this increases the storage requirements and the size of the comparator.
It would also be possible to address the branch target buffer with physical addresses. However, this approach has the disadvantage of increasing latency in detaining a branch prediction since the prediction must wait until a translation lookaside buffer lookup has been made.